package com.gzl.exercise;

import org.junit.jupiter.api.Test;

/**
 * @PROJECT_NAME: exercise
 * @NAME: 非递减数列
 * @DESCRIPTION: 中等
 * @USER: gaozengliang
 * @DATE: 2023/3/27
 */
public class 非递减数列 {
    /**
     * 给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
     * 我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
     *
     * 示例 1:
     * 输入: nums = [4,2,3]
     * 输出: true
     * 解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。
     *
     * 示例 2:
     * 输入: nums = [4,2,1]
     * 输出: false
     * 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
     *
     * 提示：
     * n == nums.length
     * 1 <= n <= 10^4
     * -10^5 <= nums[i] <= 10^5
     */

    /**
     * 分析 1 ：
     * 非递减序列：单调不减，增数列，nums[i] <= nums[i + 1] 前一个元素小于等于后一个元素
     *
     * 最多只能有 1 个 nums[i] > nums[i+1] 的存在，如果大于 1 个，直接返回 false
     *
     * 当修改不超过一个的时候
     * 如果 nums[i] > nums[i+1] ，判断是否能够通过修改让其成为非递减序列
     * 此时要么nums[i]变小，要么nums[i+1]变大
     * nums[i]可修改为 nums[i-1]（此时要保证后面非递减成立，即 nums[i-1]<=nums[i+1]，否则就失败） 或 nums[i+1]（此时要保证前面非递减仍成立，仍然是 nums[i-1]<=nums[i+1]，否则就失败），
     * nums[i+1] 可修改为 nums[i]（此时要保证后面非递减成立，即nums[i+1]<=nums[i+2]） 或 nums[i+2]（此时要保证前面非递减成立，即nums[i]<=nums[i+2]）。
     * 当这两个都不能修改的时候（nums[i-1]>nums[i+1] && nums[i+1]>nums[i+2] && nums[i]>nums[i+2]），那就返回false。
     */
    @Test
    void nds1(){
//        int[] nums = {4,2,3};
//        int[] nums = {4,2,1};
//        int[] nums = {4};
//        int[] nums = {3,4,1,2};// 预期 false，得到 true
//        int[] nums = {3,4,1,3};// 预期 false，得到 true
//        int[] nums = {3,4,1,4};
//        int[] nums = {-1,4,2,3};// 预期 true，得到 false
//        int[] nums = {5,4,2,3};
        int[] nums = {5,7,1,8}; // 预期 true，得到 false

        if (nums.length < 3){
            System.out.println("true");
            return;
        }
        int chageNum = 0;
        int n = nums.length;
        boolean isSuccess = true;
        for (int i = 0;i<n-1;i++){
            if (nums[i]>nums[i+1]){
                chageNum++;
                if (chageNum>1){
                    isSuccess = false;
                    System.out.println(chageNum);
                    System.out.println(isSuccess);
                    return;
                }
                if (i>0 && i<n-2 && nums[i-1]>nums[i+1] && nums[i]>nums[i+2]){
                    isSuccess = false;
                    System.out.println("---"+isSuccess);
                    return;
                }
            }
        }
        System.out.println(isSuccess);
    }

    /**
     * 分析 2 （此解法与 1 皆可）：
     * 非递减序列：单调不减，增数列，nums[i] <= nums[i + 1] 前一个元素小于等于后一个元素
     *
     * 循环判断 nums[i] > nums[i+1] 的个数，最多只能有 1 个 nums[i] > nums[i+1] 的存在，如果大于 1 个，直接返回 false
     *
     * 当 nums[i] > nums[i+1] 时，
     *      ① 将 nums[i+1] 的值赋给 nums[i]，此时要保证前面的非递减成立，即 nums[i-1]<=nums[i+1]，
     *      （此方法赋值后与下次判断就无关了，下次判断的是当前i的i+1和i+2的值，这次i的值就用不到了。所以在程序中该赋值方法无需体现）
     *      若修改后上述条件不成立（nums[i-1]>nums[i+1]）那么该数列肯定不是非递减序列；则需进行下方的修改：
     *      ② 将 nums[i] 的值赋给 nums[i+1]，因为 nums[i] 前面的数列肯定是非递减，现在只需接着向后方循环判断即可，如果个数超过 1 直接返回false
     */
    @Test
    void nds2(){
//        int[] nums = {4,2,3};
//        int[] nums = {4,2,1};
//        int[] nums = {4};
//        int[] nums = {3,4,1,2};// 预期 false，得到 true
//        int[] nums = {3,4,1,3};// 预期 false，得到 true
//        int[] nums = {3,4,1,4};
//        int[] nums = {-1,4,2,3};// 预期 true，得到 false
//        int[] nums = {5,4,2,3};
        int[] nums = {5,7,1,8}; // 预期 true，得到 false

        if (nums.length < 3){
            System.out.println("true");
            return;
        }
        int chageNum = 0;
        int n = nums.length;
        boolean isSuccess = true;
        for (int i = 0;i<n-1;i++){
            if (nums[i]>nums[i+1]){
                chageNum++;
                if (chageNum>1){
                    isSuccess = false;
                    System.out.println(chageNum);
                    System.out.println(isSuccess);
                    return;
                }
                if (i>0 && nums[i-1]>nums[i+1]){
                    nums[i+1] = nums[i];
                }
            }
        }
        System.out.println(isSuccess);
    }
}
